


from collections import OrderedDict


class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.data:
            return -1
        self.data.move_to_end(key,False)
        return self.data[key]


    def put(self, key: int, value: int) -> None:

        self.data[key] = value
        self.data.move_to_end(key=key, last=False)

        if len(self.data) > self.capacity:
            self.data.popitem()